#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <math.h>
#include <algorithm>
using namespace std;

vector<vector<int>>rows(9,vector<int>(10,0));
vector<vector<int>>colums(9,vector<int>(10,0));
vector<vector<int>>boxes(9,vector<int>(10,0));
bool suduSolved = false;
void backtrack(int i,int j,vector<vector<char>>& board);

bool couldPlace(int num,int row,int colum){
    int index = (row/3)*3 + colum/3;
    return (rows[row][num] + colums[colum][num] + boxes[index][num]) == 0;
}

void placeNumber(int num,int row,int colum,vector<vector<char>>& board){
    rows[row][num]++;
    colums[colum][num]++;
    int index = (row/3)*3 + colum/3;
    boxes[index][num]++;
    board[row][colum] = num + '0';
}
void removeNumber(int num,int row,int colum,vector<vector<char>>& board){
    rows[row][num]--;
    colums[colum][num]--;
    int index = (row/3)*3 + colum/3;
    boxes[index][num]--;
    board[row][colum] = '.';
}
void placeNextNumber(int row,int colum,vector<vector<char>>& board){
    if(row == 8 && colum == 8) suduSolved = true;
    else{
        if(colum == 8) backtrack(row+1,0,board);
        else backtrack(row,colum+1,board);
    }
}
void backtrack(int row,int colum,vector<vector<char>>& board){

    if(board[row][colum] == '.'){
        for(int d=1;d<=9;d++){
            if(couldPlace(d,row,colum)){
                placeNumber(d,row,colum,board);
                placeNextNumber(row,colum,board);
                if(!suduSolved) removeNumber(d,row,colum,board);
            }
        }
    }else placeNextNumber(row,colum,board);
}

void solveSudoku(vector<vector<char>>& board) {
    int temp=0;
    for(short i=0;i<9;i++){
        for(short j=0;j<9;j++){
            if(board[i][j] != '.'){
                temp = board[i][j] - '0';
                placeNumber(temp,i,j,board);
            }
        }
    }
    backtrack(0,0,board);
}

int main(){
    vector<vector<char>>board={
    {'5','3','.','.','7','.','.','.','.'},
    {'6','.','.','1','9','5','.','.','.'},
    {'.','9','8','.','.','.','.','6','.'},
    {'8','.','.','.','6','.','.','.','3'},
    {'4','.','.','8','.','3','.','.','1'},
    {'7','.','.','.','2','.','.','.','6'},
    {'.','6','.','.','.','.','2','8','.'},
    {'.','.','.','4','1','9','.','.','5'},
    {'.','.','.','.','8','.','.','7','9'}
    };
    solveSudoku(board);

    for(auto temp:board){
        for(auto tt:temp){
            cout<<tt<<"  ";
        }
        cout<<"\n";
    }

//    for(auto temp:colums){
//        for(auto tt:temp){
//            cout<<tt<<"  ";
//        }
//        cout<<"\n";
//    }
//    cout<<"\n";
//
//    for(auto temp:boxes){
//        for(auto tt:temp){
//            cout<<tt<<"  ";
//        }
//        cout<<"\n";
//    }
    return 0;
}